//
// Created by 紫霄 on 2020/5/9.
//

#ifndef LEETCODE_26_H
#define LEETCODE_26_H
#include <queue>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
  bool isSubStructure(TreeNode *A, TreeNode *B) {
    if (!B)
      return false;
    queue<TreeNode *> nodes;
    vector<TreeNode *> ans;
    nodes.push(A);
    while (!nodes.empty()) {
      TreeNode *curRoot = nodes.front();
      if (curRoot->val == B->val)
        ans.emplace_back(curRoot);
      if (curRoot->left)
        nodes.push(curRoot->left);
      if (curRoot->right)
        nodes.push(curRoot->right);
      nodes.pop();
    }
    for (auto i : ans) {
      if (isSameStructure(i, B))
        return true;
    }
    return false;
  }
  bool isSameStructure(TreeNode *A, TreeNode *B) {
    //判断两个节点是否有相同结构和数值
    if (A->val == B->val) {
      bool Bl = true;
      bool Br = true;
      if (B->left) {
        if (A->left) {
          Bl = isSameStructure(A->left, B->left);
        } else {
          Bl = false;
        }
      }
      if (B->right) {
        if (A->right) {
          Br = isSameStructure(A->right, B->right);
        } else {
          Br = false;
        }
      }
      if (!B->right && !B->left) {
        return true;
      }
      return Bl && Br;
    }
    return false;
  }
};
#endif // LEETCODE_26_H
